#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <cstdlib>

#define MAXN 10000000

using namespace std;

int map[10][10];
int n, m;

void output(string s) {
    for (int i = 0; i < s.length() - 1; i++) cout << s[i] << ",";
    cout << s[s.length() - 1] << endl;
}

vector<int> getNums() {
    string s;
    cin >> s;
    string tmp = "";
    vector<int> nums;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            tmp += s[i];
        } else {
            if (tmp != "") {
                nums.push_back(atoi(tmp.c_str()));
                tmp = "";
            }
        }
    }
    if (tmp != "") {
        nums.push_back(atoi(tmp.c_str()));
        tmp = "";
    }

    return nums;
}

string bfs() {
    int arr[101], head = 0, rear = 1, i;
    bool vis[10];
    string ans = "";
	memset(vis, 0, sizeof(vis));
    arr[0] = 1;
    vis[0] = true;
    while (head < rear) {
        for (i = 0; i < n; i++) {
            if (!vis[i] && i != arr[head] - 1 && map[i][arr[head] - 1] != 0) {
                arr[rear++] = i + 1;
                vis[i] = true;
            }
        }
        head++;
    }
    for (i = 0; i < rear - 1; i++) {
        ans += (char) (arr[i] + '0');
        ans += ',';
    }
    ans += (char) (arr[rear - 1] + '0');
    return ans;
}

bool vis[10];
int rec[10];
int step = 1;
void dfs(int last) {
    int i;
    for (i = 0; i < n; i++) {
        if (!vis[i] && map[i][last] != 0) {
            vis[i] = true;
            rec[step++] = i + 1;
            dfs(i);
            break;
        }
    }
}

int main() {
    cout << "Input" << endl;
    vector<int> data = getNums();
    n = data[0];
    m = data[1];
    
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) map[i][j] = 0;

    
    for (i = 0; i < m; i++) {
        data = getNums();
        map[data[0] - 1][data[1] - 1] = data[2];
        map[data[1] - 1][data[0] - 1] = data[2];
    }

    cout << "Output" << endl;
    cout << bfs() << endl;
    vis[0] = true;
    rec[0] = 1;
    dfs(0);
    for (i = 0; i < step - 1; i++) cout << rec[i] << ",";
    cout << rec[step - 1] << endl;

    int dist[10][10];
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            if (map[i][j] != 0) {
                dist[i][j] = map[i][j];
            } else {
                dist[i][j] = MAXN;
            }
        }

    int k;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            for (k = 0; k < n; k++) {
                if (i != j && j != k && i != k) {
                    if (dist[i][j] + dist[j][k] < dist[i][k]) {
                        dist[i][k] = dist[i][j] + dist[j][k];
                    }
                }
            }
        }
    }

    if (dist[0][n - 1] >= MAXN) {
        cout << 0 << endl;
    } else cout << dist[0][n - 1] << endl;

    cout << "End" << endl;
    return 0;
}